#include <iostream>
#include <queue>
using namespace std;
class Btree {
private:
    int val;
    Btree* left;
    Btree* right;
public:
    Btree(int v) {
        val = v;
        left = NULL;
        right = NULL;
    }
    void insert(int v) {
        if (v < val) {
            if (left == NULL) {
                left = new Btree(v);
            }
            else {
                left->insert(v);
            }
        }
        else if (v > val) {
            if (right == NULL) {
                right = new Btree(v);
            }
            else {
                right->insert(v);
            }
        }
    }
    void inorder() {
        if (left!= NULL) {
            left->inorder();
        }
        cout << val << " ";
        if (right!= NULL) {
            right->inorder();
        }
    }
    int depth();
    int b_d(Btree* root);
};
int Btree::depth() {
    if (this->left == NULL && this->right == NULL) {
        return 1;
    }
    else if (this->left == NULL) {
        return this->right->depth() + 1;
    }
    else if (this->right == NULL) {
        return this->left->depth() + 1;
    }
    
        return max(this->left->depth(), this->right->depth()) + 1;
    
}
int Btree::b_d(Btree* root){
    queue<Btree*> q;
    int res=0;
    if(root==NULL) return 0;
    Btree* temp=root;
    q.push(root);
    while(!q.empty()){
        res++;
        int size=(int)q.size();
        for(auto i=0;i<size;i++){
            temp=q.front();
            q.pop();
            if(temp->left!=NULL) q.push(temp->left);
            if(temp->right!=NULL) q.push(temp->right);
        }
    }
    return res;
}
int main() {
    Btree* root = new Btree(5);
    root->insert(3);
    root->insert(7);
    root->insert(2);
    root->insert(6);
    root->insert(8);
    root->insert(4);
    root->insert(1);
    root->inorder();
    cout << endl;
    cout << "Depth of the tree is: " << root->depth() << endl;
    cout << "Breadth of the tree is: " << root->b_d(root) << endl;
    return 0;
}